# 《最长回文子串》

# 给你一个字符串 s，找到 s 中最长的回文子串。
# 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

# 示例 1：
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。

# 示例 2：
# 输入：s = "cbbd"
# 输出："bb"
#  

# 提示：
# 1 <= s.length <= 1000
# s 仅由数字和英文字母组成
# 中心扩散、动态规划、manacher

# 暴力美学：
# 1、根据字符串长度length猜测回文子串可能长度为length~1
# 2、首先猜测回文子串长度为length，依次递减，需要猜测length次
# 3、从头到尾一一反序比对，第n次猜测，子串长度为strlen = length-(n-1)
# 4、需要比对length-strlen+1或n次
class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        for i in range(length):
            strlen = length-i
            if strlen < 2:
                return s[0]
            for j in range(i+1):
                strs = s[j:j+strlen]
                if strs == strs[::-1]:
                    return strs

# class Solution:
#     def longestPalindrome(self, s: str) -> str:
#         length = len(s)
#         for i in range(length):
#             strlen = length-i
#             if strlen < 2:
#                 return s[0]
#             for j in range(i+1):
#                 if s[j:j+strlen] == s[j:j+strlen:-1]: # 切片反序错误
#                     return s[j:j+strlen]

strs = "babad"
A = Solution()
print(A.longestPalindrome(strs))
